<!DOCTYPE html>
<html lang="zh-CN">
  <head>
  <meta charset="UTF-8">
  <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1">
  <meta http-equiv="X-UA-Compatible" content="ie=edge">
  <meta name="description" content="">
  <meta name="keywords" content="">
  
    <link rel="icon" href="/avatar.jpg">
  
    
  <title>ural-1792 Hamming Code | 科学君的不科学博客</title>
  <link rel="stylesheet" href="/style.css">
  <link rel="stylesheet" href="/lib/jquery.fancybox.min.css">
  <link href="https://maxcdn.bootstrapcdn.com/font-awesome/4.7.0/css/font-awesome.min.css">
  <script type="text/javascript" src="https://tajs.qq.com/stats?sId=65546304" charset="UTF-8"></script>
  <script>
  (function(){
      var bp = document.createElement('script');
      var curProtocol = window.location.protocol.split(':')[0];
      if (curProtocol === 'https') {
          bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
      }
      else {
          bp.src = 'http://push.zhanzhang.baidu.com/push.js';
      }
      var s = document.getElementsByTagName("script")[0];
      s.parentNode.insertBefore(bp, s);
  })();
  </script>
</head>

<body>
  <header>
  <div class="header-container">
    <a class='logo' href="/">
      <span>科学君的不科学博客</span>
    </a>
    <ul class="right-header">
      
        <li class="nav-item">
          
            <a href="/" class="item-link">首页</a>
          
        </li>
      
        <li class="nav-item">
          
            <a href="/about" class="item-link">关于</a>
          
        </li>
      
        <li class="nav-item">
          
            <a href="/archives" class="item-link">归档</a>
          
        </li>
      
        <li class="nav-item">
          
            <a href="/tags" class="item-link">标签</a>
          
        </li>
      
        <li class="nav-item">
          
            <a href="/atom.xml" class="item-link">FEED 订阅</a>
          
        </li>
      
    </ul>
  </div>
</header>

  <main id='post'>
  <div class="content">
    <article>
      <section class="content markdown-body">
        <h1>ural-1792 Hamming Code</h1>
        <div class='post-meta'>
          <i class="fa fa-calendar" aria-hidden="true"></i>
          <time>2016年07月12日</time>
          
          | <i class="fa fa-folder-open-o" aria-hidden="true"></i> 
  <div class="article-category">
    <a class="article-category-link" href="/categories/acm/">acm</a>
  </div>



          
          
          |
          
          <i class="fa fa-tag" aria-hidden="true"></i>
          
          
  <a href="/tags/#acm" class='tag'>acm</a>


          
        </div>
        <ul>
<li><a href="#sec-">题目：</a></li>
<li><a href="#sec-">代码：</a></li>
<li><a href="#sec-">解析&amp;吐槽：</a></li>
</ul>
<h1 id="题目："><a href="#题目：" class="headerlink" title="题目："></a>题目：<a id="sec-"></a></h1><p><img src="b4cf2095-2a91-4468-a5ea-72be8b54b07f.png" alt="img"></p>
<p class="verse"><br>1792. Hamming Code<br><br>Time limit: 1.0 second<br><br>Memory limit: 64 MB<br><br>Let us consider four disks intersecting as in the figure. Each of the three shapes formed by the intersection of three disks will be called a petal.<br><br>Write zero or one on each of the disks. Then write on each petal the remainder in the division by two of the sum of integers on the disks that contain this petal. For example, if there were the integers 0, 1, 0, and 1 written on the disks, then the integers written on the petals will be 0, 1, and 0 (the disks and petals are given in the order shown in the figure).<br><br>This scheme is called a Hamming code. It has an interesting property: if you enemy changes secretely any of the seven integers, you can determine uniquely which integer has been changed. Solve this problem and you will know how this can be done.<br><br>Problem illustration<br><br>Input<br><br>The only line contains seven integers separated with a space, each of them being zero or one. The first four integers are those written on the disks in the order shown in the figure. The following three integers are those written on the petals in the order shown in the figure<br><br>Output<br><br>Output one line containing seven integers separated with a space. The integers must form a Hamming code. The set of integers may differ from the input set by one integer at most. It is guaranteed that either the input set is a Hamming code or a Hamming code can be obtained from it by changing exactly one integer.<br><br>Samples<br><br></p>

<p>| input         | output        |<br>| 0 1 0 1 1 0 1 | 0 1 0 0 1 0 1 |<br>| 1 1 1 1 1 1 1 | 1 1 1 1 1 1 1 |</p>
<h1 id="代码："><a href="#代码：" class="headerlink" title="代码："></a>代码：<a id="sec-"></a></h1><figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;iostream&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;functional&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;string&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;set&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;algorithm&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> <span class="built_in">std</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> disk[<span class="number">4</span>];</span><br><span class="line"><span class="keyword">int</span> pat[<span class="number">3</span>];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">bool</span> <span class="title">ok</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> pat[<span class="number">0</span>]==(disk[<span class="number">1</span>]+disk[<span class="number">2</span>]+disk[<span class="number">3</span>])%<span class="number">2</span> &amp;&amp;</span><br><span class="line">            pat[<span class="number">1</span>]==(disk[<span class="number">0</span>]+disk[<span class="number">2</span>]+disk[<span class="number">3</span>])%<span class="number">2</span> &amp;&amp;</span><br><span class="line">            pat[<span class="number">2</span>]==(disk[<span class="number">0</span>]+disk[<span class="number">1</span>]+disk[<span class="number">3</span>])%<span class="number">2</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">inline</span> <span class="keyword">void</span> <span class="title">get</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(ok())</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;<span class="number">4</span>;++i)</span><br><span class="line">    &#123;</span><br><span class="line">        disk[i]=!disk[i];</span><br><span class="line">        <span class="keyword">if</span>(ok())</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        disk[i]=!disk[i];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;<span class="number">3</span>;++i)</span><br><span class="line">    &#123;</span><br><span class="line">        pat[i]=!pat[i];</span><br><span class="line">        <span class="keyword">if</span>(ok())</span><br><span class="line">            <span class="keyword">return</span>;</span><br><span class="line">        pat[i]=!pat[i];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">throw</span> <span class="keyword">int</span>();</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    ios::sync_with_stdio(<span class="literal">false</span>);</span><br><span class="line">    <span class="built_in">cin</span>.tie(<span class="literal">NULL</span>);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;<span class="number">4</span>;++i)</span><br><span class="line">        <span class="built_in">cin</span>&gt;&gt;disk[i];</span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;<span class="number">3</span>;++i)</span><br><span class="line">        <span class="built_in">cin</span>&gt;&gt;pat[i];</span><br><span class="line"></span><br><span class="line">    get();</span><br><span class="line"></span><br><span class="line">    <span class="keyword">for</span>(<span class="keyword">int</span> i=<span class="number">0</span>;i&lt;<span class="number">4</span>;++i)</span><br><span class="line">        <span class="built_in">cout</span> &lt;&lt; disk[i]&lt;&lt;<span class="string">' '</span>;</span><br><span class="line">    <span class="built_in">cout</span> &lt;&lt; pat[<span class="number">0</span>]&lt;&lt;<span class="string">' '</span>&lt;&lt;pat[<span class="number">1</span>]&lt;&lt;<span class="string">' '</span>&lt;&lt;pat[<span class="number">2</span>]&lt;&lt;<span class="built_in">endl</span>;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h1 id="解析-amp-吐槽："><a href="#解析-amp-吐槽：" class="headerlink" title="解析&amp;吐槽："></a>解析&amp;吐槽：<a id="sec-"></a></h1><p>每个碟片和碟片的重叠处都有一个数字，碟片的数字是 0 或 1，重叠处的数字是叠在此处的三个碟片 上数字的和除以 2 的余数。现在给出碟片和重叠处的数字，如果不符合要求，则可以改动一个数字 （碟片或重叠处的数字均可）使之符合要求，输出改正后的数字。</p>
<p>这道题很简单，只需要用穷举就可以做了。因为只需要改动一个数字，最多就只有七种情况，不需要 消耗多少时间。</p>

      </section>
      <div class="license">
        <a href="http://creativecommons.org/licenses/by-sa/3.0/" rel="license" target="_blank">
          <img src="http://i.creativecommons.org/l/by-sa/3.0/88x31.png" style="border-width:0"
               alt="Creative Commons License" class="center">
        </a>
      </div>
      <p>
        本作品采用
        <a rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" target="_blank">
          署名-相同方式共享 4.0 国际
        </a>
        进行许可。欢迎转载、使用、重新发布，但务必保留文章署名
        “不科学的科学君” (Liu233w) 与博客链接：
        <a href="https://liu233w.github.io">https://liu233w.github.io</a>
        ，基于本文修改后的作品务必以相同的许可发布。如有任何疑问，请
        <a href="mailto:wwwlsmcom@outlook.com" target="_blank">与我联系</a>
        。
      </p>
    </article>
    
    <!-- disqus 评论框 start -->
    <div class="comment">
      <div id="disqus_thread" class="disqus-thread">
        <i>加载评论框需要翻墙</i>
      </div>
    </div>
    <!-- disqus 评论框 end -->
    
    
    <!-- livere 评论框 start -->
    <div class="comment">
      <div id="lv-container" data-id="city" data-uid="MTAyMC8zNTE5NS8xMTczMA=="></div>
    </div>
    <!-- livere 评论框 end -->
    
  </div>
  <aside>
    
    <div class="toc-container">
      <h1>目录</h1>
      <div class="content">
        <ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#题目："><span class="toc-number">1.</span> <span class="toc-text">题目：</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#代码："><span class="toc-number">2.</span> <span class="toc-text">代码：</span></a></li><li class="toc-item toc-level-1"><a class="toc-link" href="#解析-amp-吐槽："><span class="toc-number">3.</span> <span class="toc-text">解析&amp;吐槽：</span></a></li></ol>
      </div>
    </div>
    
  </aside>
</main>

<!-- disqus 公共JS代码 -->
<script type="text/javascript">
  /* * * CONFIGURATION VARIABLES * * */
  var disqus_shortname = "liu233w";
  var disqus_identifier = "https://liu233w.github.io/2016/07/12/ural-1792.org/";
  var disqus_url = "https://liu233w.github.io/2016/07/12/ural-1792.org/";

  isAgent(getDisqus)

  // determine user agent in China
  function isAgent(cb) {
    var url = '//graph.facebook.com/feed?callback=h';
    var xhr = new XMLHttpRequest();
    var called = false;
    xhr.open('GET', url);
    xhr.onreadystatechange = function () {
      if (xhr.readyState === 4 && xhr.status === 200) {
        called = true;
        cb(true);
      }
    };
    xhr.send();
    // timeout 1s, this facebook API is very fast.
    setTimeout(function () {
      if (!called) {
        xhr.abort();
        cb(false)
      }
    }, 1000);
  }

  function getDisqus(isAgent) {
    var dsq = document.createElement('script');
    dsq.type = 'text/javascript';
    dsq.async = true
    dsq.src = '//' + disqus_shortname + '.disqus.com/embed.js';
    (document.getElementsByTagName('head')[0] || document.getElementsByTagName('body')[0]).appendChild(dsq)
  }
</script>
<!-- disqus 公共JS代码 end -->


<script type="text/javascript">
  (function (d, s) {
    var j, e = d.getElementsByTagName(s)[0];

    if (typeof LivereTower === 'function') {
      return;
    }

    j = d.createElement(s);
    j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
    j.async = true;

    e.parentNode.insertBefore(j, e);
  })(document, 'script');
</script>


  <footer>
  <div class="copyright">
    <div>
      &copy; 2019 | Powered by <a href="https://hexo.io" target="_blank">Hexo</a>&nbsp
    </div>
    <div>
      Theme by <a href="https://github.com/lewis-geek/hexo-theme-Aath" target="_blank">Aath</a>
    </div>
  </div>
</footer>


<script src="https://cdn.bootcss.com/jquery/3.2.1/jquery.min.js"></script>
<script src="/lib/in-view.min.js"></script>
<script src="/lib/lodash.min.js"></script>
<script>
  var isDown = true
  var oldY = 0
  inView.offset(50)

  document.body.addEventListener('touchstart', function(){});
  
  window.addEventListener('scroll', _.throttle(e => {
    var currentY = window.scrollY
    if((oldY - currentY) < 0) {
      isDown = true
    } else {
      isDown = false
    }
    oldY = currentY
  }, 250))

  $("article img").each(function() {
      var strA = "<a data-fancybox='gallery' href='" + this.src + "'></a>";
      $(this).wrapAll(strA);
  });

  $('.toc-link').each(function() {
      var href = $(this).attr("href");
      
      inView(href).on('exit', () => {
        if (isDown) {
          handleActive(href)
        }
      })

      inView(href).on('enter', () => {
        if (!isDown) {
          handleActive(href)
        }
      })

      this.onclick = function(e) {
        var pos = $(href).offset().top - 10;
        $("html,body").animate({scrollTop: pos}, 300);
        setTimeout(() => {
          handleActive(href)
        }, 350)
        return false
      }
  })

  function handleActive(href) {
    document.querySelectorAll('.toc-link').forEach(elm => {
      elm.classList.remove('active')
    })
    document.querySelector(".toc [href='"+ href +"']").classList.add('active')
  }
</script>
<script src="/lib/jquery.fancybox.min.js"></script>

<script async src="//dn-lbstatics.qbox.me/busuanzi/2.3/busuanzi.pure.mini.js"></script>

</body>
</html>
